Bandwidth management in modern high speed packet communications networks operates on two different time scales which can be called "connection level controls" and "packet level controls." Connection level controls are applied at the time the connection is set up and are based on the load characteristics of the transmission links in the connection route at the time that the connection is set up. Connection level controls include bandwidth allocation, path selection and admission control and call setup. Bandwidth allocation is accomplished by noting, at the connection setup time, the "equivalent capacity" loading that the new connection will generate, based on the traffic characteristics of the source signal and the desired quality of service. Using this equivalent capacity that must be available to carry the new connection, the originating node of the network computes a path to the destination node that is capable of carrying the new connection and providing the level of service required by the new connection. This path selection utilizes data describing the current state of the traffic in the entire network. Such data can be stored in a topology data base located at each entry point, and, indeed, each node, of the network. If no suitable path can be found to meet these requirements, the connection is rejected. Once the path has been selected, the actual end-to-end setup utilizes a setup message traversing the selected route and updating the resource allocation for each link visited by the setup message. Due to race conditions, simultaneous request for setup, or unknown changes in the link resource allocation, the attempt to set up the call may fail because of the lack of necessary resources at the time the call setup message reaches a node along the route. In general, each of the end-to-end processes, i.e., initial bandwidth allocation, route selection and call setup, requires adequate network resources to carry the call and a failure at any point in any of these processes results in the call being rejected, thus preventing the launching of packets likely to cause network overload.
At the packet level, once the connection is established and the call setup procedures completed, the steady state traffic behavior is monitored to insure that the traffic behaves in accordance with the assumptions made at call setup time and that the classes of service continue to be supported by the network. Packet level controls are applied at the network access points and typically consist of a rate control mechanism and a traffic estimation module. In addition, each intermediate node implements scheduling and packet buffering strategies which enforce the necessary classes of service for the traffic in transit. The access point packet level controls, on the other hand, monitor the incoming traffic to insure that the statistical nature of the traffic assumed at call setup time continues throughout the duration of the connection, thereby preventing overload and congestion before it occurs. In many cases, it is not possible to accurately predict, a priori, the statistical parameters associated with a traffic source. Furthermore, the traffic characteristics of a source may change substantially over time. It is therefore important to have the ability to estimate the traffic flow and to react dynamically to changes in the characteristics of the traffic on a connection.
It is essential to successful traffic management and a congestion free network that the proper interrelationship between connection level controls and packet level controls be preserved at all times. That is, the parameters of the connection level controls must be set so as to allow the desired packet level controls to operate appropriately. Similarly, the packet level control functions must be made consistent with the call setup allocations. Prior art approaches to this problem are described in "New Directions in Communications (or Which Way to the Information Age)", by J. S. Turner, IEEE Communications Magazine, Vol. 24, No. 10, pages 8-15, October 1986, "A Congestion Control Framework for High-Speed Integrated Packetized Transport," by G. M. Woodruff, R. G. H. Rogers and P. S. Richards, Proceedings of the IEEE Globcom '88, pages 203-207, November 1988, "PARIS: An Approach to Integrated High-Speed Private Networks," by I. Cidon and I. S. Gopal, Internation Journal of Digital and Analog Cabled Systems, Vol. 1, No. 2, pages 77-85, April- June 1988, "Meeting the Challenge: Congestion and Flow Control Strategies for Broadband Information Transport," by A. E. Echberg, Jr., D. T. Luan and D. M. Lucantoni, Proceedings of the IEEE Globcom '89, pages 1769-1773, March 1989, "Bandwidth Management and Congestion Control in plaNET," by I. Cidon, I. S. Gopal and R. Guerin, IEEE Communications Magazine, Vol. 29, No. 10, pages 54-63, October 1991, and "A Unified Approach to Bandwidth Allocation and Access Control in Fast Packet-Switched Networks," by R. Guerin and L. Gun, Proceedings of the IEEE Infocom '92, Florence, Italy, pages 1-12, May 1992.
In order to accommodate connections in a packet communications network for data streams with widely different characteristics, it is important to allocate bandwidth for each connection with a metric which is readily computable, easily updated and capable of capturing all of the significant characteristics of the highly diversified traffic. Moreover, this metric must also be used to characterize the accumulated transmission link traffic load due to all of the individual connections on that link. An easily calculated metric to characterize traffic on a network is a critical factor for efficient traffic control in the network. Another critical factor is the mapping of this metric into a packet level mechanism such as the "leaky bucket" type of packet control.
More specifically, a leaky bucket form of packet level access control requires the achievement of two general objectives. First, the scheme must be transparent as long as the traffic stays within the setup values, allowing immediate access to the network. Secondly, however, the leaky bucket scheme must control the maximum bandwidth taken by the user source when the source increases its traffic beyond the setup values, at least until a new bandwidth can be negotiated. The leaky bucket control mechanism operates as described below.
Tokens are generated at a fixed rate and delivered to a token pool of a fixed size. Packets are allowed to enter the network only if the number of available tokens in the token pool will accommodate the packet. Assuming, for example, that each token gives permission for the transmission of one bit of information, then a packet can enter the network only if the number of available tokens is larger than the number of bits in the packet. After each packet is launched into the network, the number of available tokens in the pool is decremented by the number of bits in the packet. Ideally, the token accumulation rate is equal to the long term average rate for this traffic while the pool size is a function of the burstiness of the traffic. Both the token rate and the pool size are chosen to achieve transparency of the leaky bucket for well-behaved user traffic, where the average rate and burstiness are as expected. The peak rate at which packets can enter the network, however, is controlled by the use of a spacer at regular intervals in the packet traffic which limit the maximum rate at which packets can be injected into the network. One such use of spacers is described in the afore-mentioned Infocom '92 article of the present applicants. In general, this maximum rate is equal to the peak rate of the traffic, but can be tuned to achieve any desired trade-off between the smoothing of the user traffic (at the cost of increased access delay) and the amount of bandwidth reserved for that traffic.
In general, the constraint of transparency requires that the token rate be greater than the average traffic rate to account for the burstiness of the input traffic. The value of the token rate then determines the worst case average rate at which the user traffic can enter the network. More particularly, when the user average input rate increases beyond the token rate, the leaky bucket will saturate, causing the token pool to be always empty. Packets can therefore only enter the network as fast as tokens are generated. The output of the leaky bucket then appears like a constant bit stream at an average rate equal to the token rate. In order to ensure that this increased average load going into the network does not create congestion, the token rate should be no greater than the bandwidth reserved for that connection in the links. Once this token rate is determined, the size of the token pool can be chosen to achieve reasonable transparency to the user of the leaky bucket. A difficult problem is the determination of these leaky bucket parameters for each connection to achieve both transparency and maximum bandwidth control and, at the same time, the computation of these parameters sufficiently quickly to permit dynamic, realtime packet level control of network traffic.